package DynamicProgramingSeries;

public class CanPartition_416 {
    public boolean canPartition_2dim(int[] nums) {

        // 将问题转化为01背包
        // 背包容量：sum/2
        // 背包放入的商品weight和value都是元素值
        // 背包装满，说明找到了总和为sum/2的子集
        // 不可重复放入元素到背包

        int sum = 0;
        for (int n : nums) {
            sum += n;
        }

        if ((sum % 2) != 0) {
            return false;
        }

        int len = nums.length;
        int target = sum / 2;
        /*
        dp[i][j]表示从数组的 [0, i] 这个子区间内挑选一些正整数
          每个数只能用一次，使得这些数的和恰好等于 j。
        */
        boolean[][] dp = new boolean[len][target + 1];

        // 先填表格第 0 行，第 1 个数只能让容积为它自己的背包恰好装满
        // 这里的dp[][]数组的含义就是“恰好”，所以就算容积比它大的也不要）
        if (nums[0] <= target) {
            dp[0][nums[0]] = true;
        }

        //初始化dp数组
        for (int i = 1; i < len; i++) {
            for (int j = 0; j <= target; j++) {
                dp[i][j] = dp[i - 1][j];

                //如果某个物品单独的重量恰好就等于背包的重量，那么也是满足dp数组的定义的
                if (nums[i] == j) {
                    dp[i][j] = true;
                    continue;
                }

                // 如果某个物品重量小于j，看能否放入背包
                if (nums[i] < j) {
                    dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i]];
                }
            }
        }
        return dp[len - 1][target];
    }

    public boolean canPartition_1dim(int[] nums) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }

        if ((sum % 2) == 1) return false;
        int target = sum / 2;

        /*
        dp[j]:任意取[0, i]的数，其和为j
        */
        int[] dp = new int[target + 1];

        for (int i = 0; i < nums.length; i++) {
            // 倒序遍历
            for (int j = target; j >= nums[i]; j--) {
                dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);
            }

            if (dp[target] == target) {
                return true;
            }
        }
        return dp[target] == target;
    }
}
